Computer systems are an integral part of real-time systems. These computers systems are "embedded" in the sense that they monitor and control other equipment in the system. Because they operate in step with the equipment, they are said to be operating in real time.
A dominant characteristic of real time systems is that the system must respond to some external stimulus within some "short" time interval. How short this interval must be depends on the nature of the problem being solved and the equipment being used. Another characteristic of a typical real time system is that it must be capable of responding to more than one external stimulus at essentially the same time.
In a real-time systems, the processes that handle system responses are referred to as "tasks". Those tasks having deadlines that must be met in this manner are referred to as "critical" tasks. In order to ensure that critical tasks meet their deadlines, the computer operating system must include an appropriate scheduling algorithm.
One approach to scheduling is that used in conventional general purpose operating systems. These systems are generally concerned with allocation of processor time. A commonly used technique is allocating processing time to application processes, using some sort of time slicing algorithm. Each time the allocated time for a process expires, the execution of that process is suspended and the next process is permitted to run.
A recent development in real-time systems is the use of memory management support software, with which the user may dynamically allocate and deallocate storage for objects. Some of these memory management tools are automatic in the sense that they determine when an application program no longer uses storage and then reclaim it. The component that performs the reclaiming service is called a "garbage collector".
In systems having automatic memory management, the capacity of the memory management process to reclaim memory is limited to a particular rate, usually expressed as bits per second. Thus, like a processor, the memory management system is a resource, whose capacity must be scheduled. If both critical and non-critical tasks consume the resource, there is a danger that a critical task may miss a deadline because it must wait to acquire a resource that has been depleted by a non-critical task.
However, conventional processor scheduling techniques are not suitable for scheduling memory allocation. In contrast to processor availability, the availability of allocated memory is a function of a rate of consumption. Also, inherent in dynamic memory allocation is the characteristic that memory consumption can change according to system conditions, and can be difficult to predict. A need exists for a method of scheduling real-time computer systems having automatic memory management so that noncritical tasks do not interfere with critical task deadlines.